package com.topcoder.srm518;

public class LargestSubsequence {
	public String getLargest(String s) {
		StringBuilder sb = new StringBuilder();
		int N = s.length();
		for (int i = 0; i < N; i++) {
			int max = i;
			for (int j = i + 1; j < N; j++) {
				if (s.charAt(max) < s.charAt(j))
					max = j;
			}
			sb.append(s.charAt(max));
			i = max;
		}
		return sb.toString();
	}

	public String getLargest2(String s) {
		String res = "";
		while (s.length() > 0) {
			for (char c = 'z';; c--)
				if (s.indexOf(c) >= 0) {
					res += c;
					s = s.substring(s.indexOf(c) + 1);
					break;
				}
		}
		return res;
	}
}
